package fun.coding.leetcode;

import java.util.HashMap;
import java.util.Map;

public class CopyListWithRandomPointer {

	public static void main(String[] args) {

	}
	
	// With the help of hashmap, key is original node, value is the newly copied node
	public RandomListNode copyRandomList(RandomListNode head) {
		Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
		
		RandomListNode dummy = new RandomListNode(-1);
		RandomListNode pre = dummy, newNode;
		
		while (head != null) {
			if (!map.containsKey(head)) {
				newNode = new RandomListNode(head.label);
				map.put(head, newNode);
			} else {
				newNode = map.get(head);
			}
			
			pre.next = newNode;
			pre = newNode;
			
			// ignore the null random pointer
			if (head.random != null) {
				if (!map.containsKey(head.random)) {
					newNode.random = new RandomListNode(head.random.label);
					map.put(head.random, newNode.random);
				} else {
					newNode.random = map.get(head.random);
				}
			}
			
			head = head.next;
		}
		
		return dummy.next;
	}
	
	/*
	//TODO: write up this method, very tricky and clever method. 
	public class Solution {
	    private void copyNext(RandomListNode head) {
	        while (head != null) {
	            RandomListNode newNode = new RandomListNode(head.label);
	            newNode.random = head.random;
	            newNode.next = head.next;
	            head.next = newNode;
	            head = head.next.next;
	        }
	    }

	    private void copyRandom(RandomListNode head) {
	        while (head != null) {
	            if (head.next.random != null) {
	                head.next.random = head.random.next;
	            }
	            head = head.next.next;
	        }
	    }

	    private RandomListNode splitList(RandomListNode head) {
	        RandomListNode newHead = head.next;
	        while (head != null) {
	            RandomListNode temp = head.next;
	            head.next = temp.next;
	            head = head.next;
	            if (temp.next != null) {
	                temp.next = temp.next.next;
	            }
	        }
	        return newHead;
	    }

	    public RandomListNode copyRandomList(RandomListNode head) {
	        if (head == null) {
	            return null;
	        }
	        copyNext(head);
	        copyRandom(head);
	        return splitList(head);
	    }
	    */

}
